package algorithm.unionfind;

import java.util.Arrays;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/5/18 07:15
 */
public class QuickUnion_rank extends QuickUnion {
    private int[] ranks;

    public QuickUnion_rank(int capacity) {
        super(capacity);
        ranks = new int[capacity];
        // 初始化，每个节点的高度都是1
//        for (int i = 0; i < ranks.length; i++) {
//            ranks[i] = 1;
//        }
        Arrays.fill(ranks, 1);
    }

    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);

        if (p1 == p2) return;

        // p1的高度小于p2的高度，将p1嫁接到p2上
        if (ranks[p1] < ranks[p2]) {
            parents[p1] = p2;
        } else if (ranks[p1] > ranks[p2]) {
            parents[p2] = p1;
        } else {
            parents[p1] = p2;
            // 高度相等时，嫁接后，高度加1
            ranks[p2]++;
        }
    }
}
